package BFS;


import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: dust
 * @Date: 2019/11/18 21:39
 */
public class SingleSourcePath {

    private Graph G;
    private boolean[] visited;
    private int[]pre;
    private int[]dis;
    private int s;

    public SingleSourcePath(Graph G,int s) {

        this.G=G;
        this.s=s;
        visited=new boolean[G.V()];
        pre=new int[G.V()];
        dis=new int[G.V()];
        for(int i=0;i<pre.length;i++){
            pre[i]=-1;
            dis[i]=-1;
        }

        bfs(s);
        for(int i=0;i<dis.length;i++){
            System.out.print(dis[i]+" ");
        }
    }

    private void bfs(int s){
        Queue<Integer>queue=new LinkedList<>();
        queue.add(s);
        visited[s]=true;
        pre[s]=s;
        dis[s]=0;
        while(!queue.isEmpty()){
            int v=queue.remove();//取出队首元素
            for(int w:G.adj(v)){
                if(!visited[w]){
                    queue.add(w);
                    visited[w]=true;
                    pre[w]=v;
                    dis[w]=dis[v]+1;
                }
            }
        }
    }

    public boolean isConnectedTo(int t){
        G.validateVertex(t);
        return visited[t];
    }

    public int dis(int t){
        G.validateVertex(t);
        return dis[t];
    }

    public Iterable<Integer> path(int t){
        ArrayList<Integer>res=new ArrayList<>();
        if(!isConnectedTo(t))return res;
        int cur=t;
        while(cur!=s){
            res.add(cur);
            cur=pre[cur];
        }
        res.add(s);
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        Graph g=new Graph("g.txt");
        SingleSourcePath graphBFS=new SingleSourcePath(g,0);
        System.out.println("0----->6 : "+graphBFS.path(6));
        System.out.println(graphBFS.dis(6));
    }

}
